package SelectSorting;

/**
 * Created with IntelliJ IDEA.
 * Description:选择排序的优化算法
 * User: 均先生
 * Date: 2023-11-19
 * Time: 15:00
 */
public class DoublePointSelectSorting {
    /**
     * 该算法相比于传统的双循环算法有几个优点:
     * 1.减少了比较次数：传统的双层循环选择排序中，内层循环每次都要比较未排序部分的所有元素，而这种算法通过同时找到最大值和最小值，减少了比较次数。
     * 2.减少了交换次数：由于同时找到最大值和最小值，每次外层循环只需要进行两次交换操作，而传统的选择排序可能需要多次交换操作。
     * 3.整体效率更高：尽管时间复杂度仍然是O(n^2)，但实际运行时由于减少了比较和交换的次数，整体效率会更高一些，尤其是在数据量比较大时。
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * @param array
     */
    public static void sort(int[] array) {
        int left = 0;
        int right = array.length-1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i < right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            swap(array,minIndex,left);
            //防止第一数就是最大值,交换完最大值就到最小值位置去了
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
